import logging
from math import *
EPSILON = 1e-6
TWOEPSILON = 2*EPSILON
def convert_to_tuple(p):
    """Convert an array p with two elements into the equivalent two element tuple"""
    return (p[0], p[1])
def float_equal(num1, num2):
    if abs(num1 - num2) > TWOEPSILON:
        return False
    return True
def nodes_equal(p_node1, p_node2):
    return points_equal(p_node1, p_node2)

def points_equal(p_point1, p_point2):
    if(p_point1 == None or p_point2 == None): return False
    return float_equal(p_point1[0], p_point2[0]) and float_equal(p_point1[1], p_point2[1])

def segments_equal(seg1, seg2):
    if seg1 == (None, None) and seg2 == (None, None): return True
    p_point1, p_point2 = seg1
    p_point3, p_point4 = seg2
    if points_equal(p_point1, p_point3) and points_equal(p_point2, p_point4): return True
    if points_equal(p_point1, p_point4) and points_equal(p_point2, p_point3): return True
    return False
def segs_equal(s1, s2):
    return segments_equal(s1, s2)

def segment(point1, point2):
    if points_equal(point1, point2):
        return None, None
    return (point1, point2)
    
class point:
    def __init__(self, x,y):
        self.x = x
        self.y = y
    def __eq__(self, other):
        return float_equal(self.x, other.x) and float_equal(self.y, other.y)

def interpolate((point1, point2), val):
    return ((1-val) * point1[0] + val * point2[0], (1-val) * point1[1] + val * point2[1])
            
def match(point,point1,point2,point3,point4):
    return points_equal(point, point1) or points_equal(point, point2) or points_equal(point, point3) or points_equal(point, point4)

def mag(p_vec):
    return sqrt(sum([i*i for i in p_vec]))

def dis(point1, point2):
    return sqrt(dis2(point1, point2))

def dis2(point1, point2):
    return (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1])    

def add_points(p1, p2):
    return [p1[i] + p2[i] for i in range(len(p1))]

def dist(n1, n2):
    return mag(subtract_points(n1, n2))

def flip_coords(point):
    if point == None:
        return None
    return (point[1], point[0])
SMALL_NUM = 0.000001
def order((n1, n2), (n3, n4)):
    if(max(dis(n1, n3), dis(n2, n4)) > max(dis(n2, n3), dis(n1, n4))):
        return (n1, n2), (n4, n3)
    return (n1, n2), (n3, n4)
def line_eq(p0, p1):
    """Given the line segment (p1, p2) return the equation of the line Ax+By+C=0 (i.e. the (A,B,C)), where A,B,C are normalized such that A^2+B^2+C^2=1"""
    A = float(p0[1] - p1[1]) #A = y0 - y1
    B = float(p1[0] - p0[0]) #B = x1 - x0
    C = float(p0[0] * p1[1] - p1[0] * p0[1]) # C = x0y1 - x1y0
    m = mag((A,B,C));
    return (A/m, B/m, C/m)
def dist_between_segs(seg1, seg2):
    """Given line segments seg1 and seg2 return the maximum magitude of the difference between their equation of the line
    that is if seg1 has line equation Ax+By+C=0 and seg2 has line equation Ex+Fy+G=0, with mag((A,B,C))=1 and mag((E,F,G))=1, then return mag((A-E, B-F,C-G))"""
    (A1, B1, C1) = line_eq(seg1[0], seg1[1]);
    (A2, B2, C2) = line_eq(seg2[0], seg2[1]);
    return min(mag((A1 - A2, B1 - B2, C1 - C2)), mag((A2 - A1, B2 - B1, C2 - C1)))

def f(p, (A, B, C)):
    """Return Ax+By+C, where x = p[0] and y = p[1]"""
    return A * p[0] + B * p[1] + C

def scalar_mult(scal, vec):
    return [scal*v for v in vec]
def clamp_segs(n1, n2, n3, n4):
    """Clamp the segment defined by (n3, n4) to (n1, n2). That is if (n1, n2) is within
    EPSILON of (n3, n4) then make the distance zero"""

    #(n1, n2), (n3, n4) = order((n1, n2), (n3, n4))
    d = dist_between_segs((n1, n2), (n3, n4))
    if logging.on('clamp_segs'):
        print 'seg1: %s, %s' % (n1, n2)
        print 'seg2: %s, %s' % (n3, n4)
        print 'dist_between_segs: %s'%(d)
    #clamping time!
    if(d < EPSILON):
        (A, B, C) = line_eq(n1, n2)
        if logging.on('clamp_segs'):
            print 'line_eq for seg1: A = %s, B = %s, C = %s' % (A, B, C)
        n3 = add_points(n3, scalar_mult(-1*f(n3, (A, B, C))/(A*A + B*B), (A, B)))
        n4 = add_points(n4, scalar_mult(-1*f(n4, (A, B, C))/(A*A + B*B), (A, B)))
        n3 = convert_to_tuple(n3)
        n4 = convert_to_tuple(n4)
    return n1, n2, n3, n4
def lineIntersection((x1, y1), (x2, y2), (_x1, _y1),(_x2, _y2)):
    x1, y1, x2, y2 = float(x1), float(y1), float(x2), float(y2), 
    _x1, _y1, _x2, _y2 = float(_x1), float(_y1), float(_x2), float(_y2)
    
    n1, n2, n3, n4 = clamp_segs((x1, y1), (x2, y2), (_x1, _y1), (_x2, _y2));
    if logging.on("lineIntersection"): logging.on("__lineIntersection2D__", True)
    return __lineIntersection2D__(n1[0], n1[1], n2[0], n2[1], n3[0], n3[1], n4[0], n4[1])

def split_overlapped_vertical_line_segments((point1, point2), (point3, point4)):
    (x1, y1) = point1
    (x2, y2) = point2
    if y2 < y1:
        x2, y2, x1, y1 = x1, y1, x2, y2
        point2, point1 = point1, point2
    (x3, y3) = point3
    (x4, y4) = point4
    if y4 < y3:
        x4, y4, x3, y3 = x3, y3, x4, y4
        point4, point3 = point3, point4
    flipped_segments = False
    if y4 < y2:
        flipped_segments = True
        (x1, y1), (x2, y2), (x3, y3), (x4, y4) = (x3, y3), (x4, y4), (x1, y1), (x2, y2)
        point1, point2, point3, point4 = point3, point4, point1, point2
    # Test to make sure the line segments are vertical
    if abs(x2 - x1) > SMALL_NUM or abs(x4-x3) > SMALL_NUM:
        raise ValueError, 'not vertical'
    # Test to make sure x values are the same in both line segments
    if abs(x3 - x1) > SMALL_NUM or abs(x3 - x2) > SMALL_NUM or abs(x4 - x2) > SMALL_NUM or abs(x4 - x2) > SMALL_NUM:
        raise ValueError, 'not parallel'
    # Test to make sure lines overlap
    if max(y1,y2) <= min(y3, y4) or min(y1,y2) >= max(y3,y4):
        seg1 = {'before_overlap': (point1, point2), 'overlap': (None, None), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': (point3, point4), 'overlap': (None, None), 'after_overlap': (None, None)}
        if flipped_segments: return seg2, seg1
        return seg1, seg2
    elif y1 < y3 and y3 < y2 < y4:
        seg1 = {'before_overlap': segment(point1, point3), 'overlap': (point3, point2), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': (None, None), 'overlap': (point3, point2), 'after_overlap': (point2, point4)}
        if flipped_segments: return seg2, seg1
        return seg1, seg2
    elif y1 < y3 and y2 == y4:
        seg1 = {'before_overlap': segment(point1, point3), 'overlap': (point3, point2), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': (None, None), 'overlap': (point3, point2), 'after_overlap': (None, None)}
        if flipped_segments: return seg2, seg1
        return seg1, seg2
    elif y1 == y3 and y3 < y2 < y4:
        seg1 = {'before_overlap': (None, None), 'overlap': (point1, point2), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': (None, None), 'overlap': (point3, point2), 'after_overlap': (point2, point4)}
        if flipped_segments: return seg2, seg1
        return seg1, seg2
    elif y1 == y3 and y2 == y4:
        seg1 = {'before_overlap': (None, None), 'overlap': (point1, point2), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': (None, None), 'overlap': (point3, point4), 'after_overlap': (None, None)}
        assert(flipped_segments == False)
        return seg1, seg2
    elif y3 < y1 and y2 < y4:
        seg1 = {'before_overlap': (None, None), 'overlap': (point1, point2), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': segment(point3, point1), 'overlap': (point1, point2), 'after_overlap': (point2, point4)}
        if flipped_segments: return seg2, seg1
        return seg1, seg2
    elif y3 < y1 and y2 == y4:
        seg1 = {'before_overlap': (None, None), 'overlap': (point1, point2), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': (point3, point1), 'overlap': (point1, point2), 'after_overlap': (None, None)}
        if flipped_segments: return seg2, seg1
        return seg1, seg2
    else:
        assert(1 == 0)
def split_overlapped_horizontal_line_segments((point1, point2), (point3, point4)):
    #Flipped horizontal line segments are vertical, so flip the line segments
    (x1, y1), (x2, y2), (x3, y3), (x4, y4) = point1, point2, point3, point4
    (_y1, _x1), (_y2, _x2), (_y3, _x3), (_y4, _x4) = point1, point2, point3, point4

    #Apply the function for vertically overlapped line segments
    seg1, seg2 = split_overlapped_vertical_line_segments(((_x1, _y1),(_x2, _y2)), ((_x3, _y3), (_x4, _y4)))

    (n1, n2) = seg1['before_overlap']
    (n3, n4) = seg1['overlap'] 
    (n5, n6) = seg1['after_overlap'] 
    
    (n7, n8) = seg2['before_overlap']
    (n9, n10) = seg2['overlap']
    (n11, n12) = seg2['after_overlap']
    
    #Flip the line segments back horizontal
    nseg1={'before_overlap': (flip_coords(n1), flip_coords(n2)), 'overlap': (flip_coords(n3), flip_coords(n4)), 'after_overlap': (flip_coords(n5), flip_coords(n6))}
    nseg2={'before_overlap': (flip_coords(n7), flip_coords(n8)), 'overlap': (flip_coords(n9), flip_coords(n10)), 'after_overlap': (flip_coords(n11), flip_coords(n12))}
    return nseg1, nseg2
def split_overlapped_parallel_line_segments((point1, point2), (point3, point4)):


    # Test to make sure the lines are not vertical or horizontal
    if abs(point1[0] - point2[0]) < SMALL_NUM or abs(point1[1] - point2[1]) <SMALL_NUM or abs(point3[0] - point4[0]) < SMALL_NUM or abs(point3[1] - point4[1]) < SMALL_NUM:
        raise ValueError

    # Arrange it so the x value of  point2  is greater than the x value of point1 and similarly for point4 and point3.
    if point2[0] < point1[0]: point2, point1 = point1, point2
    if point4[0] < point3[0]: point4, point3 = point3, point4


    slope1 = float(point2[1] - point1[1])/float(point2[0] - point1[0])
    slope2 = float(point4[1] - point3[1])/float(point4[0] - point3[0])

    # Test for parallelism
    if abs(slope1 - slope2) > SMALL_NUM:
        print "Error parallelism"
        return None, None
    
    
    y_intercept1 = point1[1] - slope1 * point1[0]
    y_intercept2 = point2[1] - slope2 * point2[0]

    # Test for same y-intercept
    if not float_equal(y_intercept1, y_intercept2):
        print "Error different y intercepts"
        print "y_intercept1, y_intercept2 = %f, %f" % (y_intercept1, y_intercept2)
        return None, None

    #Bounding box test
    if max(point1[0], point2[0]) + EPSILON < min(point3[0], point4[0]) or min(point1[0], point2[0]) > max(point3[0], point4[0]) + EPSILON:
        print "Error bounding box"
        return None, None
    
    # Case 1, [point1[0], point2[0]] is a subset of [point3[0], point4[0]]
    if point3[0] - TWOEPSILON <= point1[0] - EPSILON <= point4[0] and point3[0] - TWOEPSILON <= point2[0] - EPSILON <= point4[0]:
        seg1 = {'before_overlap': (None, None), 'overlap': (point1, point2), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': segment(point3, point1), 'overlap': (point1, point2), 'after_overlap': segment(point2, point4)}
    # Case 2, [point3[0], point4[0]] is a subset of [point1[0], point2[0]]
    elif point1[0] - TWOEPSILON <= point3[0] - EPSILON <= point4[0] and point1[0] - TWOEPSILON <= point4[0] - EPSILON <= point2[0]:
        seg1 = {'before_overlap': segment(point1, point3), 'overlap': (point3, point4), 'after_overlap': segment(point4, point2)}
        seg2 = {'before_overlap': (None, None), 'overlap': (point3, point4), 'after_overlap': (None, None)}
    # Case 3, [point1[0], point2[0]] overlaps [point3[0], point4[0]] and point4[0] < point2[0]
    elif point3[0] - TWOEPSILON < point1[0] - EPSILON < point4[0] and point4[0] - EPSILON < point2[0]:
        seg1 = {'before_overlap': (None, None), 'overlap': (point1, point4), 'after_overlap': segment(point4, point2)}
        seg2 = {'before_overlap': segment(point3, point1), 'overlap': (point1, point4), 'after_overlap': (None, None)}
    # Case 4, [point1[0], point2[0]] overlaps [point3[0], point4[0]] and point1[0] < point3[0]
    elif point1[0] - EPSILON < point3[0] and point3[0] - TWOEPSILON < point2[0] - EPSILON < point4[0]:
        seg1 = {'before_overlap': segment(point1, point3), 'overlap': (point3, point2), 'after_overlap': (None, None)}
        seg2 = {'before_overlap': (None, None), 'overlap': (point3, point2), 'after_overlap': segment(point2, point4)}
    else:
        # Should never happen
        assert(0==1)
        return None, None
    return seg1, seg2
#Modified version of http://en.wikibooks.org/wiki/Blender_3D:_Blending_Into_Python/Cookbook#2D_Line_Intersection
def __lineIntersection2D__(x1, y1, x2, y2, _x1, _y1, _x2, _y2):
        # Bounding box intersection first.
        if (min(x1, x2) - max(_x1, _x2)) > EPSILON or \
        (-max(x1, x2) + min(_x1, _x2)) > EPSILON or \
        (min(y1, y2) - max(_y1, _y2)) > EPSILON or \
        (-max(y1, y2) + min(_y1, _y2)) > EPSILON:
            return None, None # Basic Bounds intersection TEST returns false.
        
        # are either of the segments points? Check Seg1
        if abs(x1 - x2) + abs(y1 - y2) <= SMALL_NUM:
            return None, None
        
        # are either of the segments points? Check Seg2
        if abs(_x1 - _x2) + abs(_y1 - _y2) <= SMALL_NUM:
            return None, None
        flipped_segments = False
        # Make sure the HOZ/Vert Line Comes first.
        if abs(_x1 - _x2) < SMALL_NUM or abs(_y1 - _y2) < SMALL_NUM:
            flipped_segments = True
            x1, x2, y1, y2, _x1, _x2, _y1, _y2 = _x1, _x2, _y1, _y2, x1, x2, y1, y2
        # Make sure that x1 <= x2
        if x2 < x1:
            x1, y1, x2, y2 = x2, y2, x1, y1
        # Make sure that _x1 <= _x2
        if _x2 < _x1:
            _x1, _y1, _x2, _y2 = _x2, _y2, _x1, _y1
        point1=(x1,y1)
        point2=(x2,y2)
        point3=(_x1,_y1)
        point4=(_x2,_y2)
        if flipped_segments == True:
            point1, point2, point3, point4 = point3, point4, point1, point2
        
        if abs(x2-x1) < SMALL_NUM: # VERTICLE LINE
                if abs(_x2-_x1) < SMALL_NUM: # VERTICLE LINE SEG2
                    if abs(_x2-x2) < SMALL_NUM: # Lines have same x-intercept
                        #return None, 111 # 2 verticle lines dont intersect.
                        if y1 < _y1 and y1 < _y2 and y2 < _y1 and y2 < _y2: 
                            return None, None
                        if y1 > _y1 and y1 > _y2 and y2 > _y1 and y2 > _y2: 
                            return None, None
                        if max(y1, y2) == min(_y1, _y2):
                            return (x1, max(y1, y2)), {'endpoint intersection': True, 'intersection': True}
                        if max(_y1, _y2) == min(y1, y2):
                            return (_x1, max(_y1, _y2)), {'endpoint intersection': True, 'intersection': True}                        
                        if logging.on("__lineIntersection2D__"):
                            logging.log("t1")
                        return (None, None), {'overlapped intersection': split_overlapped_vertical_line_segments((point1, point2), (point3, point4)),'intersection': True}
                    else:
                        return None, None
                yi = ((_y1 / abs(_x1 - _x2)) * abs(_x2 - x1)) + ((_y2 / abs(_x1 - _x2)) * abs(_x1 - x1))
                if yi > max(y1, y2): # New point above seg1's vert line
                    return None, None
                elif yi < min(y1, y2): # New point below seg1's vert line
                    return None, None
                if match((x1,yi),point1,point2,point3,point4):
                    return (x1, yi), {'endpoint intersection': True, 'intersection': True} # Intersecting.
                else:
                    return (x1,yi), {'intersection': True}
        
        if abs(y2-y1) < SMALL_NUM: # HOZ LINE
                if abs(_y2-_y1) < SMALL_NUM: # HOZ LINE SEG2
                        #return None, 121 # 2 hoz lines dont intersect.
                        if x1<_x1 and x1<_x2 and x2<_x1 and x2<_x2: 
                            return None, None
                        if x1>_x1 and x1>_x2 and x2>_x1 and x2>_x2: 
                            return None, None
                        if max(x1, x2) == min(_x1, _x2):
                            return (max(x1, x2), y1), {'endpoint intersection': True, 'intersection': True}
                        if max(_x1, _x2) == min(x1, x2):
                            return (max(_x1, _x2), _y1), {'endpoint intersection': True, 'intersection': True}

                        if logging.on("__lineIntersection2D__"):
                            logging.log("t2")
                        return (None, y1), {'overlapped intersection': split_overlapped_horizontal_line_segments((point1, point2), (point3, point4)), 'intersection': True}
                # Can skip vert line check for seg 2 since its covered above.   
                xi = ((_x1 / abs(_y1 - _y2)) * abs(_y2 - y1)) + ((_x2 / abs(_y1 - _y2)) * abs(_y1 - y1))
                if xi > max(x1, x2): # New point right of seg1's hoz line
                    return None, None
                elif xi < min(x1, x2): # New point left of seg1's hoz line
                    return None, None
                if match((xi,y1),point1,point2,point3,point4):
                    return (xi, y1),{'endpoint intersection': True, 'intersection': True} # Intersecting.
                else:
                    return (xi,y1), {'intersection': True}
        # Accounted for hoz/vert lines. Go on with both angular.
        #Slope of line1
        b1 = (y2-y1)/(x2-x1)
        #Slope of line2
        b2 = (_y2-_y1)/(_x2-_x1)
        #Y-intercept of line1
        a1 = y1-b1*x1
        #Y-intercept of line2
        a2 = _y1-b2*_x1
        
        #Check for parallel lines.
        if abs(b1 - b2) < EPSILON:
            #Lines have different y-intercepts so they can't intersect
            if abs(a1 - a2) >= EPSILON:
                return None, None
            #Check for overlap
            if min(_x1, _x2) > max(x1, x2):
                return None, None
            if max(_x1, _x2) < min(x1, x2):
                return None, None
            
            if x1 == _x2:
                    return (x1, y1), {'endpoint intersection': True, 'intersection': True}
            elif x2 == _x1:
                    return (x2, y2), {'endpoint intersection': True, 'intersection': True}
            if abs(x2 - x1) > abs(_x2 - _x1):    
                if min(x1, x2) <= _x1 and max(x1, x2) >= _x1:

                    if logging.on("__lineIntersection2D__"):
                        logging.log("t3")
                        print "split_overlapped_parallel_line_segments:"
                        print "seg1 = " + str((point1, point2))
                        print "seg2 = " + str((point3, point4))
                    return (None, None), {'overlapped intersection': split_overlapped_parallel_line_segments((point1, point2), (point3, point4)), 'intersection': True}
                elif min(x1, x2) <= _x2 and max(x1, x2) >= _x2:

                    if logging.on("__lineIntersection2D__"):
                        logging.log("t4")

                    return (None, None), {'overlapped intersection': split_overlapped_parallel_line_segments((point1, point2), (point3, point4)), 'intersection': True}
                return None, None

            if min(_x1, _x2) <= x1 and max(_x1, _x2) >= x1:

                if logging.on("__lineIntersection2D__"):
                    logging.log("t5")

                return (None, None), {'overlapped intersection': split_overlapped_parallel_line_segments((point1, point2), (point3, point4)), 'intersection': True}
            if min(_x1, _x2) <= x2 and max(_x1, _x2) >= x2:

                if logging.on("__lineIntersection2D__"):
                    logging.log("t6")

                return (None, None), {'overlapped intersection': split_overlapped_parallel_line_segments((point1, point2), (point3, point4)), 'intersection': True}
            return None, None
            
             
        xi = - (a1-a2)/(b1-b2)
        yi = a1+b1*xi
        if (x1-xi)*(xi-x2) >= 0 and (_x1-xi)*(xi-_x2) >= 0 and (y1-yi)*(yi-y2) >= 0 and (_y1-yi)*(yi-_y2)>=0:
            if match((xi,yi),point1,point2,point3,point4):
                return (xi,yi), {'endpoint intersection': True, 'intersection': True}
            else:
                return (xi, yi),{'intersection': True}
        else:
            return None, None

def inside_shape((x, y),shape):
    """Return true if the point (x,y) is strictly inside the shape, return false otherwise
    note the return value could be true or false if the point is on the boundary
    """
    for (x1, y1) in shape.points:
        if points_equal((x, y), (x1, y1)): return False
    #The general idea is to shoot a horizontal ray and if it intersects an odd
    #number of times with the shape
    #then it is inside, otherwise it is outside(Jordan curve theory). 
    n=0
    for ((x1, y1),(x2, y2)) in shape.line_segments:
        if x2 < x1:
            x1, y1, x2, y2 = x2, y2, x1, y1

        if (y1 == y or y2 == y) and y1 != y2:
            intersection_point = (x1, y1)
            if y2 == y:
                intersection_point = (x2, y2)
            if x <= intersection_point[0]:
                if y1 == y and y1 < y2:
                    n = n + 1
                elif y1 == y and y2 < y1:
                    n = n
                elif y2 == y and y1 < y2:
                    n = n
                elif y2 == y and y2 < y1:
                    n = n + 1
                else: assert(1==0)
            continue
        if max(y1, y2) < y: continue
        if max(y1, y2) > y and min(y1, y2) > y: continue
        if max(y1, y2) > y and min(y1, y2) < y and min(x1, x2) > x:
            n=n+1
            continue
        if max(y1, y2) > y and min(y1, y2) < y:
            if abs(x2 - x1) < SMALL_NUM:
                if x1 > x:
                    n = n + 1
                    continue
            else:
                slope = (y2 - y1)/(x2 - x1)
                val_at_x = slope * (x -x1) + y1
                if ((val_at_x > y and slope <= 0) or (val_at_x < y and slope >=0)) and x1 <= x <= x2:
                    n = n + 1

    if n%2==1: return True
    return False

def on_boundary((x, y),shape):
    """Return true if the point is on the boundary of the shape, otherwise return false"""
    for (x0,y0) in shape.points:
        if abs(x0-x)+abs(y0-y)<EPSILON:
            return True
    for ((x1,y1),(x2,y2)) in shape.line_segments:
        #Bounding box test
        if min(x1,x2) - x >= EPSILON or x - max(x1,x2) >= EPSILON or min(y1,y2) - y >= EPSILON or  y - max(y1,y2) >= EPSILON:
            continue
        #Vertical line segment
        if abs(x2 - x1) < EPSILON and abs(x - x1) < EPSILON and min(y1, y2) <= y <= max(y1, y2):
            return True
        #Horizontal line segment
        if abs(y2 - y1) < 2 * SMALL_NUM and abs(y-y1) + abs(y-y2) < SMALL_NUM and min(x1,x2) <= x <= max(x1,x2):
            return True
        #Now for the non-vertical or horizontal line segment
        #If x2<x1 then flip points
        if x2<x1:
            x1,y1,x2,y2=x2,y2,x1,y1
        slope=(y2-y1)/(x2-x1)
        y_delta=slope*(x-x1)
        if abs(y-(y1+y_delta))<SMALL_NUM: return True
    return False
def segment_contained_in((p_point1, p_point2), p_shape):
    if p_point1 == None and p_point2 == None: return True
    if not ((inside_shape(p_point1, p_shape) or on_boundary(p_point1, p_shape)) and (inside_shape(p_point2, p_shape) or on_boundary(p_point2, p_shape))):
        return False
    for (point3,point4) in p_shape.line_segments:
        val1, val2 = lineIntersection(p_point1,p_point2,point3,point4)
        if val1 == None and val2 == None:
            point = interpolate((p_point1, p_point2), 0.5)
            if not (inside_shape(point, p_shape) or on_boundary(point, p_shape)):
                return False
            # No intersection so continue
            continue
        assert('intersection' in val2 and val2['intersection'] == True)
        if val2 == {'intersection': True}:
            return False
        elif 'endpoint intersection' in val2:
            intersection_point = val1
            if intersection_point == None or intersection_point == (None, None):
                print "Error in segment_contained_in returning false"
                return False
            if logging.on("segment_contained_in"):
                logging.log("p_point1 = " + str(p_point1))
                logging.log("p_point2 = " + str(p_point2))
                logging.log("point3 = " + str(point3))
                logging.log("point4 = " + str(point4))
                logging.log("intersection_point = " + str(intersection_point))
                
            if points_equal(intersection_point, p_point1) or points_equal(intersection_point, p_point2):                
                x = (p_point1[0] + p_point2[0])/2.0
                y = (p_point1[1] + p_point2[1])/2.0

                if logging.on("segment_contained_in"):
                    logging.log("point_equal")
                    logging.log("x, y = %.20f, %.20f" % (x, y))
                    logging.log("inside_shape(x,y) = %s" % (inside_shape((x, y), p_shape)))
                    logging.log("on_boundary(x,y) = %s" % (on_boundary((x, y), p_shape)))

                if inside_shape((x, y), p_shape) or on_boundary((x, y), p_shape):
                    continue
                else:
                    return False
                
            if points_equal(intersection_point, point3) or points_equal(intersection_point, point4):
                if not segment_contained_in((p_point1, point3), p_shape) or not segment_contained_in((point3, p_point2), 
                                                                                                   p_shape):
                    return False
                else:
                    continue
            print "Error invalid intersection point"
            return False
        elif 'overlapped intersection' in val2:
            seg1, seg2 = val2['overlapped intersection']
            if seg1 == None or seg2 == None: 
                print "(p_point1, p_point2):" + str(p_point1) +", " + str(p_point2)
                print "p_shape.line_segments:" + str(p_shape.line_segments)
                print "val1:" + str(val1)
                print "val2:" + str(val2)
                assert(1 == 0)   
            (n1, n2) = seg1['before_overlap']
            (n3, n4) = seg1['overlap']
            (n5, n6) = seg1['after_overlap']
            
            (m1, m2) = seg2['before_overlap']
            (m3, m4) = seg2['overlap']
            (m5, m6) = seg2['after_overlap']


            assert(segments_equal((n3, n4), (m3, m4)))           
            # The overlapped segment is contained in the shape, so we need to test the non-overlapped segments
            if segment_contained_in((n1, n2), p_shape) and segment_contained_in((n5, n6), p_shape):
            #and segment_contained_in((m1, m2), p_shape) and segment_contained_in((m5, m6), p_shape):
                continue
            else:
                return False
        else: assert(1==0)
    return True
def segment_inside((p_point1, p_point2), p_shape):
    if p_point1 == None and p_point2 == None: return True
    if not ((inside_shape(p_point1,p_shape) or on_boundary(p_point1, p_shape)) and (inside_shape(p_point2,p_shape) or on_boundary(p_point2, p_shape))):
        return False  
    for (point3,point4) in p_shape.line_segments:
        val1, val2 = lineIntersection(p_point1,p_point2,point3,point4)
        if val1 == None and val2 == None:
            point = interpolate((p_point1, p_point2), 0.5)
            if not (inside_shape(point, p_shape) or on_boundary(point, p_shape)):
                return False
            # No intersection so continue
            continue
        assert('intersection' in val2 and val2['intersection'] == True)
        if val2 == {'intersection': True}:
            return False
        elif 'endpoint intersection' in val2:
            intersection_point = val1
            if intersection_point == None or intersection_point == (None, None):
                print "Error in segment_contained_in returning false"
                return False
                        
            if points_equal(intersection_point, p_point1) or points_equal(intersection_point, p_point2):
                   x = (p_point1[0] + p_point2[0])/2.0
                   y = (p_point1[1] + p_point2[1])/2.0
                   if inside_shape((x, y), p_shape) or on_boundary((x, y), p_shape):
                       continue
                   else:
                       return False

            return False
        elif 'overlapped intersection' in val2:
            return False
        else: assert(1==0)
        return False
    return True
def segment_on_boundary((p_point1, p_point2), p_shape):
    if p_point1 == None and p_point2 == None: return True
    if not (on_boundary(p_point1, p_shape) and on_boundary(p_point2, p_shape) and on_boundary(interpolate((p_point1, p_point2), 0.5), p_shape)):
        return False
    for (point3,point4) in p_shape.line_segments:
        val1, val2 = lineIntersection(p_point1,p_point2,point3,point4)
        if val1 == None and val2 == None:
            point = interpolate((p_point1, p_point2), 0.5)
            if not (inside_shape(point, p_shape) or on_boundary(point, p_shape)):
                return False
            # No intersection so continue
            continue
        assert('intersection' in val2 and val2['intersection'] == True)
        if val2 == {'intersection': True}:
            return False
        elif 'endpoint intersection' in val2:
            intersection_point = val1
            if intersection_point == None or intersection_point == (None, None):
                print "Error in segment_contained_in returning false"
                return False
                        
            if points_equal(intersection_point, p_point1) or points_equal(intersection_point, p_point2):
                   x = (p_point1[0] + p_point2[0])/2.0
                   y = (p_point1[1] + p_point2[1])/2.0
                   if inside_shape((x, y), p_shape) or on_boundary((x, y), p_shape):
                       continue
                   else:
                       return False

            return False

        elif 'overlapped intersection' in val2:
           seg1, seg2 = val2['overlapped intersection']
           if seg1 == None or seg2 == None: assert(1 == 0)
           (n1, n2) = seg1['before_overlap']
           (n3, n4) = seg1['overlap']
           (n5, n6) = seg1['after_overlap']

           (m1, m2) = seg2['before_overlap']
           (m3, m4) = seg2['overlap']
           (m5, m6) = seg2['after_overlap']
           assert(segments_equal((n3, n4), (m3, m4)))
           # The overlapped segment is on the boundary so we need to test the non-overlapped segments
           if segment_on_boundary((n1, n2), p_shape) and segment_on_boundary((n5, n6), p_shape):
               #and segment_on_boundary((m1,m2), p_shape) and segment_on_boundary((m5, m6), p_shape):
               return True
           else:
               return False
        else: assert(1==0)
    return True
def segment_outside((p_point1, p_point2), p_shape):
    if p_point1 == None and p_point2 == None: return True
    if (inside_shape(p_point1, p_shape) and not on_boundary(p_point1, p_shape)) or (inside_shape(p_point2, p_shape) and not on_boundary(p_point2, p_shape)) or (inside_shape(interpolate((p_point1, p_point2), 0.5), p_shape) and not on_boundary(interpolate((p_point1, p_point2), 0.5), p_shape)):
        return False
    for (point3,point4) in p_shape.line_segments:
        val1, val2 = lineIntersection(p_point1,p_point2,point3,point4)
        if val1 == None and val2 == None:
            point = interpolate((p_point1, p_point2), 0.5)
            if inside_shape(point, p_shape):
                return False
            # No intersection so continue
            continue
        assert('intersection' in val2 and val2['intersection'] == True)
        if val2 == {'intersection': True}:
            print '(point3, point4):%s, %s'%(point3, point4)
            return False
        elif 'endpoint intersection' in val2:
            x = (p_point1[0] + p_point2[0])/2.0
            y = (p_point1[1] + p_point2[1])/2.0
            
            if inside_shape((x, y), p_shape):
                return False
            else:
                continue
        elif 'overlapped intersection' in val2:
            return False

        else: assert(1==0)
    return True
#Split a line segment into the parts that are inside p_shape, the parts that are on the boundary of p_shape, and the parts that are outside p_shape
def split_segment((p_point1, p_point2), p_shape):
    return_val={'inside': [], 'boundary': [], 'outside': []}
    if p_point1 == None and p_point2 == None: return return_val
    if segment_on_boundary((p_point1, p_point2), p_shape):
        return {'inside': [], 'boundary': [(p_point1, p_point2)], 'outside': []}
    if segment_inside((p_point1, p_point2), p_shape):
        return {'inside': [(p_point1, p_point2)], 'boundary': [], 'outside': []}
    if  segment_outside((p_point1, p_point2), p_shape):
        return {'inside': [], 'boundary': [], 'outside': [(p_point1, p_point2)]}

    
    for (point3,point4) in p_shape.line_segments:
        val1, val2 = lineIntersection(p_point1, p_point2, point3, point4)
        if val1 == None and val2 == None:
            # No intersection so continue
            continue
        assert('intersection' in val2 and val2['intersection'] == True)
        if val2 == {'intersection': True}:
            intersection_point = val1
            split1 = split_segment((p_point1, intersection_point), p_shape)
            split2 = split_segment((intersection_point, p_point2), p_shape)            
            return_val['inside'].extend(split1['inside'])
            return_val['inside'].extend(split2['inside'])
            return_val['boundary'].extend(split1['boundary'])
            return_val['boundary'].extend(split2['boundary'])

            return_val['outside'].extend(split1['outside'])
            return_val['outside'].extend(split2['outside'])

            return return_val
        elif 'endpoint intersection' in val2:
            intersection_point = val1
            if intersection_point == None or intersection_point == (None, None):
                print "Error in split_segment returning continuing"
                continue
            if points_equal(intersection_point, p_point1) or points_equal(intersection_point, p_point2):
                continue
            else:
                intersection_point = val1
                split1 = split_segment((p_point1, intersection_point), p_shape)
                split2 = split_segment((intersection_point, p_point2), p_shape)            
                return_val['inside'].extend(split1['inside'])
                return_val['inside'].extend(split2['inside'])
                return_val['boundary'].extend(split1['boundary'])
                return_val['boundary'].extend(split2['boundary'])
                
                return_val['outside'].extend(split1['outside'])
                return_val['outside'].extend(split2['outside'])

                return return_val
            continue
        elif 'overlapped intersection' in val2:
            seg1, seg2 = val2['overlapped intersection']
            if seg1 == None or seg2 == None: assert(1 == 0)
               

            (n1, n2) = seg1['before_overlap']
            (n3, n4) = seg1['overlap']
            (n5, n6) = seg1['after_overlap']

            (m1, m2) = seg2['before_overlap']
            (m3, m4) = seg2['overlap']
            (m5, m6) = seg2['after_overlap']
            assert(segments_equal((n3, n4), (m3, m4)))
            return_val['boundary'].append((n3,n4))
           
            if n2 == p_point1: n1, n2 == n2, n1
            if n5 == p_point2: n5, n6 == n6, n5

            if m2 == p_point1: m1, m2 == m2, m1
            if m5 == p_point2: m5, m6 == m6, m5
            split1 = split_segment((n1, n2), p_shape)
            split2 = split_segment((n5, n6), p_shape)
            return_val['boundary'].extend(split1['boundary'])
            return_val['boundary'].extend(split2['boundary'])

    
            return_val['inside'].extend(split1['inside'])
            return_val['inside'].extend(split2['inside'])

            return_val['outside'].extend(split1['outside'])
            return_val['outside'].extend(split2['outside'])
            return return_val
           # The overlapped segment is on the boundary so we need to test the non-overlapped segments
           #if segment_on_boundary((n1, n2), p_shape) and segment_on_boundary((n3, n4), p_shape) and segment_on_boundary((m1,m2), p_shape) and segment_on_boundary((m5, m6)):
           #    return True
           #else:
           #    return False
        else:
            assert(1==0)
